package Sort;

public class Sort2 {
//从小到大排
    public void selectmin(int[]array){
        for (int i = 0; i <array.length-1 ; i++) {
            int min=i;
            for (int j = i+1; j <array.length ; j++) {
if(array[j]<array[min]){
    min=j;
}
            }
            swap(array,i,min);
        }
    }
    //从大到小排
    public void selectmax(int[]array){
        for (int i = 0; i <array.length-1 ; i++) {
            int max=i;
            for (int j = i+1; j <array.length ; j++) {
                if(array[j]>array[max]){
                    max=j;
                }
            }
            swap(array,i,max);
        }
    }

    public void select(int[]array){
        int left=0,right=array.length-1;
        for(;left<right;left++,right--){
            int min=left;
            int max=left;
            for (int i = left+1; i <=right ; i++) {
                if(array[i]>array[max]){
                    max=i;
                }
                if(array[i]<array[min]){
                    min=i;
                }
            }
            swap(array,left,min);
            if(max==left){
                max=min;
            }
            swap(array,right,max);
        }
    }

    public void quickSort(int[]array){
        quick(array,0,array.length-1);
    }


    private void quick(int[]array,int start,int end){
if(start>=end){
    return;
}
int pivot=partition1(array,start,end);
quick(array,start,pivot-1);
quick(array,pivot+1,end);
    }


    private int partition1(int[]array,int left,int right){
        int tmp=array[left];
        int prv=left;
        int cur=left+1;
        while(cur<=right){
            if(array[cur]<=tmp&&(++prv)!=cur){
                swap(array,prv,cur);
            }
            cur++;
        }
        swap(array,left,prv);
        return prv;
    }



    private int partition(int[]array,int start,int end){
        int tmp=array[start];
        while (start<end){
            while(start<end&&array[end]>=tmp){
                end--;
            }
            array[start]=array[end];
            while(start<end&&array[start]<=tmp){
                start++;
            }
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }


    private int partitionHoare(int[]array,int left,int right){
        int tmp=array[left];
        int lefttmp=left;
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            while(left<right&&array[left]<=tmp){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,lefttmp,left);
return left;
    }


public void heapSort(int[]array){
create(array);
    for (int i = array.length-1; i >0 ; i--) {
        swap(array,0,i);
        sifDown(array,0,i);
    }


}
    private void create(int[]array){
for (int parent=(array.length-2)/2;parent>=0;parent--){
    sifDown(array,parent,array.length);
}


    }


    private void sifDown(int[]array,int parent,int len){
        int child=parent*2+1;
     while(child<len){
         if(child+1<len&&array[child]<array[child+1]){
             child++;
         }
         if(array[child]>array[parent]){
             swap(array,parent,child);
             parent=child;
             child=parent*2+1;
         }else {
             break;
         }
     }
    }



    private void swap(int[]array,int left,int right){
        int tmp=array[left];
        array[left]=array[right];
        array[right]=tmp;
    }
}
